package C006;

import java.util.Arrays;

/**
 * ClassName: FindLeft
 * Package: C005
 * Description:
 *
 * @Author BCXJ
 * @Create 2024/11/28 14:16
 * @Version 1.0
 * @Since 1.0
 */
public class FindRight {

    public static void main(String[] args) {
        int n = 10000;
        int length = 50;
        int maxSize = 100;
        for (int i = 0; i < n; i++) {
            int[] arr = generateRandomArray(length, maxSize);
            Arrays.sort(arr);
            int target = (int) (Math.random() * length);
            int index1 = violenceOperation(arr, target);
            int index2 = findRight(arr, target);
            if(index2 != index1){
                System.out.println("error!!!");
                System.out.println(Arrays.toString(arr));
                System.out.println(target);
                System.out.println(index1);
                System.out.println(index2);
                return;
            }
        }
        System.out.println("success!!!");
    }

    public static int[] generateRandomArray(int n, int max) {
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * max);
        }
        return arr;
    }


    public static int violenceOperation(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] <= target && arr[i + 1] > target) {
                return i;
            }
        }
        return -1;
    }


    public static int findRight(int[] arr, int target) {
        if(arr.length == 0) {
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        int midIndex = 0;
        int res = -1;
        while (left <= right) {
            midIndex = left + ((right - left) >> 1);
            if(arr[midIndex] > target) {
                right = midIndex - 1;
            }else if(arr[midIndex] <= target) {
                res = midIndex;
                left = midIndex + 1;
            }
        }
        return res;
    }
}